package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

public class _offer68_1_bst_lca {
    
    /**
     * 有序能帮到我什么？
     * bisection!
     * 1. root 太大，去 root 左边
     * 2. root 太小，去 root 右边
     * 3. root 在 p q 中间，怎么办？返回？
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > q.val) return lowestCommonAncestor(root, q, p);
        if (root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
    
}
